package com.mystudy.leetcode.problem.tree.p_110;

/**
 * @program: infoalgorithm
 * @description: 平衡二叉树
 * @author: zhouzhilong
 * @create: 2019-08-09 16:04
 **/

import com.mystudy.leetcode.base.TreeNode;
import com.mystudy.leetcode.base.TreeNodeUtils;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
 * <p>
 * 本题中，一棵高度平衡二叉树定义为：
 * <p>
 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
 * <p>
 * 示例 1:
 * <p>
 * 给定二叉树 [3,9,20,null,null,15,7]
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回 true 。
 * <p>
 * 示例 2:
 * <p>
 * 给定二叉树 [1,2,2,3,3,null,null,4,4]
 * <p>
 * 1
 * / \
 * 2   2
 * / \
 * 3   3
 * / \
 * 4   4
 * 返回 false 。
 */
public class Solution {
    private static final Logger LOGGER = LoggerFactory.getLogger(Solution.class);

    long startTime = 0L;
    long endTime = 0L;


    @Before
    public void before() {
        startTime = System.nanoTime();
    }

    @Test
    public void test() {
        TreeNode root = TreeNodeUtils.generateTwoTrees(new Integer[]{1, 2, 2, 3, 3, null, null, 4, 4});
        boolean balanced = isBalanced(root);
        LOGGER.debug("balanced = [{}]",balanced);
    }

    @After
    public void after() {
        endTime = System.nanoTime();
        double cost = (endTime - startTime) / 1000000.0;
        LOGGER.debug("cost = [{} ms ]",cost);
    }


    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        return Math.abs(leftDepth-rightDepth)<=1 && isBalanced(root.left) && isBalanced(root.right);

    }

    private int getDepth(TreeNode node) {
        if(node == null){
            return 0;
        }
        int leftHeight = getDepth(node.left);
        int rightHeight = getDepth(node.right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

}
